package leetcode每日一题;


import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 账户合并 {
    // 定义并查集
    class UnionFind {
        int maxsize;
        int[] root;
        int[] rank;

        public UnionFind(int n) {
            maxsize = n;
            root = new int[n];
            rank = new int[n];
            for(int i = 0; i < n; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int x) {
            if(root[x] == x) {
                return x;
            }
            return find(root[x]);
        }

        public void union(int x,int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY) {
                if(rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                }
                else if(rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                }
                else if(rank[rootX] == rank[rootY]) {
                    root[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int eamilCounts = 0; // 记录所有的邮箱
        HashMap<String,Integer> emailToIndex = new HashMap<>(); // 邮箱:索引
        HashMap<String,String> emailToName = new HashMap<>(); // 邮箱:账户名
        // 初始化上述定义的两个哈希表
        for(List<String> account : accounts) { // 扫描每个账户信息集合
            // 注意：每个账户集合中所有的邮箱对应的都是同一个用户名
            String name = account.get(0); // 先将用户名提取出来，避免代码冗余
            // 扫描当前账户中的所有邮箱
            for(int i = 1; i < account.size(); i++) {
                String email = account.get(i); // 当前账户第i个邮箱
                if(!emailToIndex.containsKey(email)) {
                    // 如果当前邮箱不在map中
                    emailToIndex.put(email,eamilCounts++);
                    emailToName.put(email,name);
                }
            }
        }
        // 创建并查集对象
        UnionFind uf = new UnionFind(eamilCounts);
        // 合并
        for(List<String> account : accounts) {
            String firstemail = account.get(1);
            int firstIndex = emailToIndex.get(firstemail);
            for(int i = 2; i < account.size(); i++) {
                String nextemail = account.get(i);
                int nextIndex = emailToIndex.get(nextemail);
                uf.union(firstIndex,nextIndex); // 合并
            }
        }

        HashMap<Integer,List<String>> indexToEmails = new HashMap<>();
        for(String email : emailToIndex.keySet()) { // 扫描所有不相同邮箱
            int index = uf.find(emailToIndex.get(email)); // 获取当前邮箱的根节点索引
            List<String> account = indexToEmails.getOrDefault(index,new ArrayList<String>());
            account.add(email);
            indexToEmails.put(index,account);
        }

        List<List<String>> merged = new ArrayList<List<String>>(); // 存放结果
        for (List<String> emails : indexToEmails.values()) { // 扫描所有的邮箱集合
            Collections.sort(emails); // 为什么需要sort
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<String>();
            account.add(name);
            account.addAll(emails);
            merged.add(account);
        }
        return merged;
    }

    public static void main(String[] args) {
        System.out.println(Math.pow(2, 31) - 1);
    }


}
